\section{Implementação}

Neste trabalho é apresentada uma implementação do algoritmo de otimização {com/por/sei_la?} colônia de formigas para solução do 
problema de seleção de características, escrita na linguagem C. A implementação utiliza a abordagem tipo filtro para avaliação das soluções durante a otimização e um 
classificador é utilizado para avaliar a solução final. Os passos do laço principal de otimização podem ser observados no pseudo-código abaixo.


%colocar no formaato de codigo do latex

optimizeACO()
	elite[] = 0
	bestSol[] = 0
	h().eval = 0
	
	while(h().eval < MAX)
		for all Ants
			ant.sol[] = inherit(elite[])

			ant.sol[] = buildway(alpha, beta)

			ant.fitness = h(ant.sol[])
			
			if LOCAL_SEARCH
				ant.sol[] = localSearch()


		endfor

		rankAnts()

		elite[] = selElite()

		updateBestSol(bestSol[])

		updateTrail()

	endwhile

	? return bestSol[] ?

endoptimizeACO

%secoes sao na verdade paragrafos, portanto não separei mas deixei o texto comentado para guiar a escrita...
%As seções seguintes serão dedicadas para descrever a representação das informações, o detalhamento das funções de herança da elite, construção de caminho, avaliacão da qualidade da solução, busca local e atualização do feromônio.


O programa recebe como entrada uma base de dados para treinamento e um valor referente a importância individual 
da característica na base. Além da matriz para representar a base e o vetor com a importância das característica, 
é mantida uma matriz quadrada de ferômonios com o tamanho igual ao número de características. Um vetor binário representa 
uma solução. Uma posição como o valor um indica que a respectiva característica foi selecionada e o valor zero que não foi.

A solução inicial de uma formiga começa com características herdadas das soluções que formam a elite da iteração anterior. 
Uma probabilidade de herança é definida, portanto para cada característica selecionada por uma das formigas que formam a elite na iteração anterior, existe uma
probabilidade definida de essa característica ser herdada na solução de cada formiga na iteração atual. Na primeira iteração, não existe nenhuma característica
selecionada na elite, portanto nenhuma característica é herdada e as soluções começam vazias.

Na fase de contrução, novas características são selecionadas, complementando a solução herdada. Uma função heurística de construção avalia a importância individual
de uma característica considerando os valores na matriz de feromônio e o valor da característica no vetor de importância individual. Nesta implementação, os dois valores recebem pesos iguais. Ao contrário da matriz de feromônio, que evolui durante o processo de otimização, o vetor de imoprtância individual das características permanece 
estático, com os valores obtidos utilizando a função chi-quadrao (REFERENCIA) do framework weka(REFERENCIA). 

As características são analisadas em uma ordem pseudo-aleatória e são selecionadas se o valor da função heurística de construção é maior ou igual à média dos valores
da mesma função para as características já selecionadas. Quando uma formiga seleciona uma característica durante a fase de construção, ela deposita imediatamente
uma pequena quantidade de feremônio na matriz. Esse depósito já pode influênciar a construção das soluções das formigas nessa mesma iteração.

%na apresentacao comentar algumas variacoes, aqui nao precisa

O processo de busca local tem como objetivo conseguir melhoras de forma rápida com pequenas modificações. A busca sempre avança quando encontra uma melhora e termina
imediatamente quando nenhuma das três possibilidades de modificação causa melhora na solução. As três modificações são:
%na apresentacao podemos fazer a arvorezinha com tres ramificacoes...
\begin{enumerate}
	\item remover uma característica existente;
    \item adicionar uma nova característica; 
	\item trocar uma característica, ou seja, remover uma e adicionar outra.
\end

As características para remoção, adição ou troca são definidas aleatoriamente. A função utilizada para avaliar as soluções durante a busca local é a mesma 
utilizada na avaliação para a atualização de feromônios.

%na apresentacao falar das duas e dizer que testamos fazendo uma divisao entre elas mas que isso selecionava caracteristica demais...
A implementação utiliza uma abordagem do tipo filtro, a função heurística utilizada na busca local e na avaliação das soluções para atualização da matriz 
de feromônios é a distância inter(ou como a aurora diz, extra)-classe. % Lucas pode explicar melhor essa parte e REFERENCIAR a dissertacao que a prof passou


%depois de falar das distancia das classes:
Após a avaliação da qualidade das soluções de cada formiga, elas são organizadas em odem não decrescente. As formigas melhores colocadas formam o conjunto de elite. 
Apenas as formigas do conjunto elite atualizam a matriz de feromônios. A quantidade de feromônio depositado depende da colocação da formiga no conjunto elite e da 
relação da qualidade de sua solução e da melhor solução encontrada até o momento. Imediatamente após o deposito do feromônio, ocorre a evaporação. O tamanho do conjunto 
elite foi definido como 1/5  da quantidade total de formigas e a taxa de evaporação foi fixada em 5\%. 

A matriz de feromônios é inicializada com valores próximos a 0.15, com uma pequena variação aleatória. Os valores da trilha variam entre 0 e 1. 
Na fase de autalização da trilha de feromônio, o 
valor calculado por cada formiga do conjunto elite para depósito é inserido nas entradas relacionadas da matriz. Para cada característica selecionada \emph{i}, a 
\emph{i}-ésima linha da matriz é atualizada nas \emph{j}-ésimas colunas, para cada característica \emph{j} selecionada simultâneamente a característica \emph{i}.
%na apresentacao podemos fazer uma matriz e mostrar um exemplo

O número de avaliações utilizando a função heurística do tipo filtro é contabilizado. Quando esse valor atinge o valor máximo configurado, o processo de 
otimização termina e a melhor solução é retornada. % Lucas pode falar sobre a avaliacao da solucao final utilizando weka e naivebayes 
